package JzOffer.jz48;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author 张取
 * @version 1.0
 * @date 2022/1/22 下午6:32
 * JzOffer.jz48
 */

public class Codec03 {
    //前序遍历非递归
    public String serialize(TreeNode root){
        //空树
        if(root == null){
            return "";
        }
        // 用于遍历二叉树的辅助栈
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 保存结果
        StringBuilder res = new StringBuilder();
        TreeNode curNode = root;
        while(curNode != null || !stack.isEmpty()){
            while(curNode != null){
                // 根
                res.append(String.valueOf(curNode.val));
                res.append(",");
                stack.offerLast(curNode);
                //左子树
                curNode = curNode.left;
            }
            res.append("null,");
            curNode = stack.pollLast();
            //右子树
            curNode = curNode.right;
        }
        res.append("null");
        // System.out.println("res: " + res);
        return res.toString();
    }

    public TreeNode deserialize(String data){
        if(data == ""){
            return null;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        // 根据分隔符生成节点数组
        String[] nodeList = data.split(",");
        // 处理根节点
        TreeNode root = new TreeNode(Integer.parseInt(nodeList[0]));
        TreeNode curNode = root;
        int idx = 1;
        while(curNode != null || !stack.isEmpty()){
            while(curNode != null){
                stack.offerLast(curNode);
                if(!nodeList[idx].equals("null")){
                    // 处理当前节点的左孩子
                    curNode.left = new TreeNode(Integer.parseInt(nodeList[idx]));
                    // stack.offerLast(curNode.left);
                }
                // 左子树
                curNode = curNode.left;
                idx++;
            }
            curNode = stack.pollLast();
            if(!nodeList[idx].equals("null")){
                // 处理当前节点的右孩子
                curNode.right = new TreeNode(Integer.parseInt(nodeList[idx]));
                // stack.offerLast(curNode.right);
            }
            // 有子树
            curNode = curNode.right;
            idx++;
        }
        return root;
    }
}
